Crypto CTF 2022: Starter ECC (crypto)
問題概要
整数剰余類環$ \mathbb{Z}/n\mathbb{Z}上の楕円曲線において、法$ nが合成数のときx座標からy座標を求めよ。 問題スクリプト
code:sage
from Crypto.Util.number import *
from secret import n, a, b, x, flag
y = bytes_to_long(flag.encode('utf-8'))
assert y < n
E = EllipticCurve(Zmod(n), a, b) try:
G = E(x, y)
print(f'x = {x}')
print(f'a = {a}')
print(f'b = {b}')
print(f'n = {n}')
print('Find the flag :P')
except:
print('Ooops, ERROR :-(')
解法
SageMathには環上の楕円曲線に対してx座標からy座標を求める.lift_x()（docs）があるので、とりあえずこれを使う。 code:sage
E = EllipticCurve(Zmod(n), a, b) E.lift_x(x)
が、実行が終わらない。実行を中断してみると、ell_generic.pyのif D.is_square()の箇所で止まっていることがわかった。$ D=(a_1x+a_3)^2 + 4((x+a_2)x+a_4))らしいが、これがsqrt()できるかのチェックが終わらない。lift_x()を今回の楕円曲線に合わせてシンプルにしてみた。 code:sage
def lift_x(E, x, all=False):
a1, a2, a3, a4, a6 = E.ainvs()
assert a1.is_zero() and a3.is_zero()
f = ((x + a2) * x + a4) * x + a6
K = E.base_ring()
x += K(0)
one = x.parent()(1)
if f.is_square():
if all:
ys = f.sqrt(all=True)
return [E.point(x, y, one, check=False) for y in ys] else:
これを実行すると、先程と同様にf.is_square()の実行が終わらない。コードを読むと結局lift_xの処理の本質は.sqrt()で平方剰余を求めている部分だということがわかる。 なぜ平方剰余が終わらないのかを調べるため、とりあえず$ nを素因数分解してみる。
code:sage
import collections
factors = ecm.factor(n)
collections.Counter(factors)
結果はCounter({2: 63, 690712633549859897233: 6, 651132262883189171676209466993073: 5})であり、法$ nに$ 2^{63}が含まれている。平方剰余は奇素数$ pとして$ p^kでは高速に求められるが2の冪乗（$ 2^{63}）はそうではない、ということだろうか。
試しに以下を試すとすぐに終わった。
code:sage
E2 = EllipticCurve(Zmod(690712633549859897233 ** 6), a, b) E2.lift_x(x, all=True)
code:sage
E3 = EllipticCurve(Zmod(651132262883189171676209466993073 ** 5), a, b) E3.lift_x(x, all=True)
もしZmod(2**63)の場合の結果を求められたら、中国剰余定理で$ yを求めることができそうである。具体的には、 $ y = Y_1 \mod 2^{63}
$ y = Y_2 \mod 690712633549859897233^6
$ y = Y_3 \mod 651132262883189171676209466993073^5
となるような$ yを求めればよく、$ Y_2,Y_3は.lift_x()で既に求まっているため、$ Y_1さえ求めてしまえば良い。
2の冪乗の場合について調べていたが、ここでZmod(2**63)(x**3+a*x+b).nth_root(2, all=True)を実行してみるとすぐに終わることがわかった。どうやら現状のsqrt()は法が2の冪乗の整数剰余類環に対して上手く実行できないらしく、このコミットで実行できるようになったがまた追加されたばかりでリリース待ちらしい。 そこで、以下のコードを書いた。
code:sage
import itertools
from Crypto.Util.number import *
A = []
N = []
y2 = x**3 + a*x + b
for p, k in collections.Counter(factors).items():
n_ = p ** k
a_ = Zmod(n_)(y2).nth_root(2, all=True)
A.append(a_)
N.append(n_)
for t in itertools.product(*A):
y = crt(list(map(int, t)), N)
flag = long_to_bytes(y)
if b"CCTF" in flag:
print(flag)
Flag: CCTF{8E4uTy_0f_L1f7iN9_cOm3_Up!!}
余談